0837-新 21 点

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:15:46 2023-09-13 16:15:46 Updated    

爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：

爱丽丝以 0 分开始，并在她的得分少于 k 分时抽取数字。 抽取时，她从 [1, maxPts] 的范围中随机获得一个整数作为分数进行累计，其中
maxPts 是一个整数。 每次抽取都是独立的，其结果具有相同的概率。

当爱丽丝获得 k 分 或更多分 时，她就停止抽取数字。

爱丽丝的分数不超过 n 的概率是多少？

与实际答案误差不超过 10-5 的答案将被视为正确答案。

示例 1：

**输入：** n = 10, k = 1, maxPts = 10
**输出：** 1.00000
**解释：** 爱丽丝得到一张牌，然后停止。

示例 2：

**输入：** n = 6, k = 1, maxPts = 10
**输出：** 0.60000
**解释：** 爱丽丝得到一张牌，然后停止。 在 10 种可能性中的 6 种情况下，她的得分不超过 6 分。

示例 3：

**输入：** n = 21, k = 17, maxPts = 10
**输出：** 0.73278

提示：

  • 0 <= k <= n <= 104
  • 1 <= maxPts <= 104

📺视频题解

837. 新21点 4.mp4

📖文字题解

方法一：动态规划

爱丽丝获胜的概率只和下一轮开始前的得分有关，因此根据得分计算概率。

令 dp}[x] 表示从得分为 x 的情况开始游戏并且获胜的概率，目标是求 dp}[0] 的值。

根据规则，当分数达到或超过 k 时游戏结束，游戏结束时，如果分数不超过 n 则获胜，如果分数超过 n 则失败。因此当 k \le x \le \min(n, k+\textit{maxPts}-1) 时有 dp}[x]=1，当 x>\min(n, k+\textit{maxPts}-1) 时有 dp}[x]=0。

为什么分界线是 \min(n, k+\textit{maxPts}-1)？首先，只有在分数不超过 n 时才算获胜；其次，可以达到的最大分数为 k+\textit{maxPts}-1，即在最后一次抽取数字之前的分数为 k-1，并且抽到了 maxPts。

当 0 \le x < k 时，如何计算 dp}[x] 的值？注意到每次在范围 [1, \textit{maxPts}] 内随机抽取一个整数，且每个整数被抽取到的概率相等，因此可以得到如下状态转移方程：

\textit{dp}[x]=\sum_{i=1}^\textit{maxPts} \textit{dp}[x+i]}{\textit{maxPts}}

根据状态转移方程，可以实现如下简单的动态规划：

[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public double new21Game(int n, int k, int maxPts) {
        if (k == 0) {
            return 1.0;
        }
        double[] dp = new double[k + maxPts];
        for (int i = k; i <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
        }
        for (int i = k - 1; i >= 0; i--) {
            for (int j = 1; j <= maxPts; j++) {
                dp[i] += dp[i + j] / maxPts;
            }
        }
        return dp[0];
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public double New21Game(int n, int k, int maxPts) {
        if (k == 0) {
            return 1.0;
        }
        double[] dp = new double[k + maxPts];
        for (int i = k; i <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
        }
        for (int i = k - 1; i >= 0; i--) {
            for (int j = 1; j <= maxPts; j++) {
                dp[i] += dp[i + j] / maxPts;
            }
        }
        return dp[0];
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        if (k == 0) {
            return 1.0;
        }
        vector<double> dp(k + maxPts);
        for (int i = k; i <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
        }
        for (int i = k - 1; i >= 0; i--) {
            for (int j = 1; j <= maxPts; j++) {
                dp[i] += dp[i + j] / maxPts;
            }
        }
        return dp[0];
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0:
            return 1.0
        dp = [0.0] * (k + maxPts)
        for i in range(k, min(n, k + maxPts - 1) + 1):
            dp[i] = 1.0
        for i in range(k - 1, -1, -1):
            for j in range(1, maxPts + 1):
                dp[i] += dp[i + j] / maxPts
        return dp[0]
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func new21Game(n int, k int, maxPts int) float64 {
    if k == 0 {
        return 1.0
    }
    dp := make([]float64, k + maxPts)
    for i := k; i <= n && i < k + maxPts; i++ {
        dp[i] = 1.0
    }
    for i := k - 1; i >= 0; i-- {
        for j := 1; j <= maxPts; j++ {
            dp[i] += dp[i + j] / float64(maxPts)
        }
    }
    return dp[0]
}

上述解法的时间复杂度是 O(n+k \times \textit{maxPts})，会超出时间限制，因此需要优化。

考虑对 dp 的相邻项计算差分，有如下结果：

\textit{dp}[x] - \textit{dp}[x+1]=\textit{dp}[x+1] - \textit{dp}[x+\textit{maxPts}+1]}{\textit{maxPts}}

其中 0 \le x<k-1。

因此可以得到新的状态转移方程：

\textit{dp}[x]=\textit{dp}[x+1]-\textit{dp}[x+\textit{maxPts}+1]-\textit{dp}[x+1]}{\textit{maxPts}}

其中 0 \le x<k-1。

注意到上述状态转移方程中 x 的取值范围，当 x=k-1 时不适用。因此对于 dp}[k-1] 的值，需要通过

\textit{dp}[k-1]=\sum_{i=0}^{\textit{maxPts}-1} \textit{dp}[k+i]}{\textit{maxPts}}

计算得到。注意到只有当 k \le x \le \min(n, k+\textit{maxPts}-1) 时才有 dp}[x]=1，因此

\textit{dp}[k-1]=\min(n, k+\textit{maxPts}-1) - k + 1}{\textit{maxPts}} = \min(n-k+1,\textit{maxPts})}{\textit{maxPts}}

可在 O(1) 时间内计算得到 dp}[k-1] 的值。

对于 dp}[k-2] 到 dp}[0] 的值，则可通过新的状态转移方程得到。

[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public double new21Game(int n, int k, int maxPts) {
        if (k == 0) {
            return 1.0;
        }
        double[] dp = new double[k + maxPts];
        for (int i = k; i <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
        }
        dp[k - 1] = 1.0 * Math.min(n - k + 1, maxPts) / maxPts;
        for (int i = k - 2; i >= 0; i--) {
            dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts;
        }
        return dp[0];
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public double New21Game(int n, int k, int maxPts) {
        if (k == 0) {
            return 1.0;
        }
        double[] dp = new double[k + maxPts];
        for (int i = k; i <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
        }
        dp[k - 1] = 1.0 * Math.Min(n - k + 1, maxPts) / maxPts;
        for (int i = k - 2; i >= 0; i--) {
            dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts;
        }
        return dp[0];
    }
}
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        if (k == 0) {
            return 1.0;
        }
        vector<double> dp(k + maxPts);
        for (int i = k; i <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
        }
        dp[k - 1] = 1.0 * min(n - k + 1, maxPts) / maxPts;
        for (int i = k - 2; i >= 0; i--) {
            dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts;
        }
        return dp[0];
    }
};
[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0:
            return 1.0
        dp = [0.0] * (k + maxPts)
        for i in range(k, min(n, k + maxPts - 1) + 1):
            dp[i] = 1.0
        dp[k - 1] = float(min(n - k + 1, maxPts)) / maxPts
        for i in range(k - 2, -1, -1):
            dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts
        return dp[0]
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func new21Game(n int, k int, maxPts int) float64 {
    if k == 0 {
        return 1.0
    }
    dp := make([]float64, k + maxPts)
    for i := k; i <= n && i < k + maxPts; i++ {
        dp[i] = 1.0
    }

    dp[k - 1] = 1.0 * float64(min(n - k + 1, maxPts)) / float64(maxPts)
    for i := k - 2; i >= 0; i-- {
        dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / float64(maxPts) 
    }
    return dp[0]
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

复杂度分析

  • 时间复杂度：O(\min(n, k+\textit{maxPts}))。即需要计算的 dp 值的数量 \min(n, k+\textit{maxPts}-1)。

  • 空间复杂度：O(k+\textit{maxPts})。创建了一个长度为 k+\textit{maxPts 的数组 dp。

 Comments
On this page
0837-新 21 点
  1. 📺视频题解
  2. 📖文字题解